package 代码随想录.链表.环形链表;

import com.sun.xml.internal.txw2.output.IndentingXMLFilter;

import java.util.List;

/**
 * lc:142. 环形链表 II
 * link：https://leetcode-cn.com/problems/linked-list-cycle-ii/
 *
 * @author ChenweiLin
 * @create 2021-12-14 10:53
 */
public class LinkedListCycleii {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(3);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(0);
        ListNode listNode4 = new ListNode(-4);

        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode2;

        ListNode listNode = detectCycle(listNode1);
        System.out.println(listNode.val);
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public static ListNode detectCycle(ListNode head) {
        //特殊情况:空链表
        if(head == null)
            return null;

        //快慢指针
        ListNode fast = head;
        ListNode low  = head;

        while (fast.next != null && fast.next.next !=null){
            fast = fast.next.next;
            low = low.next;
            if(fast == low){//快慢指针相交
                //相交后从相交点和头节点各自发一个速度为1的指针
                ListNode index1 = fast;
                ListNode index2 = head;
                while (index1 != index2){
                    //相遇时即为环入口
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }

        }

        return null;
    }
}
